﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>

//x 1---> D
//1、如下程序的运行结果是（ ）
//char c[5] = { 'a', 'b', '\0', 'c', '\0' };
//printf("%s", c);


//x 2  --> D
//2、若有定义： int a[2][3]; ，以下选项中对 a 数组元素正确引用的是（ ）
//A : a[2][0] B : a[2][3] C : a[0][3] D : a[1 > 2][1]


//x 3  ---> D
//3、在下面的字符数组定义中，哪一个有语法错误（ ）
//int pivotIndex(int* nums, int numsSize) {
//}
//char c[5] = { 'a', 'b', '\0', 'c', '\0' };
//printf("%s", c);
//A : char a[20] = "abcdefg"; B: char a[] = "x+y=5."; C: char a[15]; D: char a[10] = '5';


//x 4 ---> A C   D：C99中支持，n是变量，不能作为数组下标
//4、下列定义数组的语句中正确的是【多选】（ ）
//A :
//#define size 10
//char str1[size], str2[size + 2];
//B: char str[]; C: int num['10']; D: int n = 5; int a[n][n + 2];


//x 5 --> B C      D是标准的指针形式访问二维数组的一个元素  数组名代表数组首元素地址
//					二维数组名代表的是第一行数组元素的地址
//5、已知 i，j 都是整型变量，下列表达式中，与下标引用 X[i][j] 不等效的是【多选】（ ）
//A : *(X[i] + j) B : *(X + i)[j] C : *(X + i + j) D : *(*(X + i) + j)




//b 1
//HJ10 字符个数统计
//描述
//编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内(0~127 ，包括 0 和 127)，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
//例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
//数据范围： 1≤n≤500 1≤n≤500
//输入描述：
//输入一行没有空格的字符串。
//输出描述：
//输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。
//输入：abc
//输出：3
//https://www.nowcoder.com/practice/eb94f6a5b2ba49c6ac72d40b5ce95f50?tpId=37&&tqId=21233&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
//int count_char(char* arr)
//{
//    int count = 0;
//    char table[128] = { 0 };
//    while (*arr != '\0')
//    {
//        if (table[*arr] != 1)
//        {
//            count++;
//            table[*arr] = 1;
//        }
//        arr++;
//    }
//    return count;
//}
//int main()
//{
//    char arr[501] = { 0 };
//    scanf("%s", arr);
//    int ret = count_char(arr);
//    printf("%d\n", ret);
//    return 0;
//}

//int count_char(char* arr)
//{
//    int count = 0;
//    char table[128] = { 0 };
//    while (*arr != '\0')
//    {
//        if (table[*arr] != 1)
//        {
//            count++;
//          //table[*arr++] = 1; //不能放里面，因为如果有重复元素的话 ++就无法执行了，指针不能向后移动了 
//        }
//        table[*arr++] = 1;   //或者这样
//    }
//    return count;
//}
//int main()
//{
//    char arr[501] = { 0 };
//    scanf("%s", arr);
//    int ret = count_char(arr);
//    printf("%d\n", ret);
//    return 0;
//}




//b 2
//169. 多数元素  --摩尔投票法 算法
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：nums = [3, 2, 3]
//输出：3
//https://leetcode.cn/problems/majority-element/

//摩尔投票法 首先先假设最大的元素是第一个元素，再用count统计。如[2,2,1,1,1,2,2]
//假设最多数是2，向后遍历，如果和2相等，count+1,如果不等count-1，当count=0的时候
//说明前面的元素抵消了，然后假设新的最大数是下一个数1，一直重复，直到最后留下的count>0 还有那个数tmp就是存在的多数元素
//int majorityElement(int* nums, int numsSize)
//{
//    int count = 0;
//    int i = 0;
//    int tmp = nums[0];
//    for (i = 0; i < numsSize; i++)
//    {
//        if (tmp == nums[i])
//        {
//            count++;
//        }
//        else
//        {
//            count--;
//        }
//        if (count == 0)
//        {
//            tmp = nums[i + 1];
//        }
//    }
//    return tmp;
//}





//D9
//x 1 --> 12
// int* p[4]是指针数组  p[3] = &a[9] -- > 10 , p[3][2] = *(p[3] + 2)
//1、下列程序的输出是（ ）
//int main()
//{
//	int a[12] = { 1,2,3,4,5,6,7,8,9,10,11,12 }， * p[4], i;
//	for (i = 0; i < 4; i++)
//		p[i] = &a[i * 3];
//	printf("%d\n"，p[3][2]);
//	return 0;
//}




//*****   x 2   ******/ -->  A
// 也就是一个元素占1个字节 4 - 9 五行。假设每行有 n 个元素 那么 0x21c-0x140 = 5*n + 9 - 4
// 算出 n=43.  4-7一共是三行。所以 0x140 + 43*3 + 7 - 4 = 0x1c4
// 
//2、二维数组X按行顺序存储，其中每个元素占1个存储单元。若 X[4][4] 的存储地址为 Oxf8b82140, X[9][9] 的存储地
//址为 Oxf8b8221c, 则 X[7][7] 的存储地址为（ ）
//A : Oxf8b821c4 B : Oxf8b821a6 C : Oxf8b82198 D : Oxf8b821c0



//x 3 -->  A
//3、以下哪个选项可以正确描述 sizeof(double) （ ）
//A : 一个整型表达式 B : 一个双精度型表达式 C : 一个不合法的表达式 D : 一种函数调用


//x 4 --> b b  **×**
// 1.先加加再打印  2.先使用赋值后 a再加加
//4、下列代码运行后的结果是什么（ ）
//int main()
//{
//	char a = 'a', b;
//	printf("%c,", ++a);
//	printf("%c\n", b = a++);
//	return 0;
//}


//x 5 --> A  ***×***
// 逗号表达式是从前到后依次计算表达式，而其结果是最后一项的值，此题去掉括号后的表达式，
//和原表达式是等价的，先计算4 * 5并赋值给x，x变为20，中间x * 5并没有改变x的值，
//最后一项x + 5值是25，也就是整个表达式的值
// 
//5、以下逗号表达式的值为（ ）
//(x = 4 * 5, x * 5), x + 5;
//A: 25 B : 20 C : 100 D : 45



//b 1
//728. 自除数
//自除数 是指可以被它包含的每一位数整除的数。
//例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
//自除数 不允许包含 0 。
//给定两个整数 left 和 right ，返回一个列表，列表的元素是范围[left, right] 内所有的 自除数 。
//输入：left = 1, right = 22
//输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
//https://leetcode.cn/problems/self-dividing-numbers/submissions/
//int* selfDividingNumbers(int left, int right, int* returnSize)
//{
//    *returnSize = 0;
//    int* ret = (int*)calloc(1000, sizeof(int));
//    int i = 0;
//    for (i = left; i <= right; i++)
//    {
//        int n = i; //i在后面会改变->0  所以需要n保留一下
//        while (n)
//        {
//            int remainder = n % 10;  //计算余数
//            if (remainder == 0 || (i % remainder) != 0)  //要注意是与原来的数判断
//                break;
//            n /= 10; //去掉一位
//        }
//        if (n == 0)
//        {
//            ret[*returnSize] = i;
//            (*returnSize)++; //要括号 不然先++ 在解引用 会非法访问
//        }
//    }
//    return ret;
//}




//b 2
//238. 除自身以外数组的乘积
//给你一个整数数组 nums，返回 数组 answer ，
//其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//请不要使用除法，且在 O(n) 时间复杂度内完成此题。
//示例 1:
//输入: nums = [1, 2, 3, 4]
//输出 : [24, 12, 8, 6]
//https://leetcode.cn/problems/product-of-array-except-self/


//更优解法：将乘积分为两次进行，第一次先将每个位置左边的数据乘积计算出来放到返回数组中，后边第二次循环将
//对应位置右边的数据乘积计算出来与返回数组对应位置的左半边乘积相乘得到结果。
//示例： 一个数组 int nums[] = { 2, 3, 4 } 。
//int left = 1, right = 1;
//计算左侧乘积：
//第0个元素的左边乘积， arr[0] = left 然后计算第1位左侧乘积 left *= nums[0]->left = 1 * 2
//第1个元素的左边乘积， arr[1] = left 然后计算第2位左侧乘积 left *= nums[1]->left = 1 * 2 * 3
//第2个元素的左边乘积， arr[2] = left 然后计算第3位左侧乘积 已经没必要了，因为第2元素是末尾元素了
//一次循环完毕后，返回数组中每个元素存储的都是自己左侧元素的乘积。 arr[]中的值：[1, 2, 6]
//计算右侧乘积：
//第2个元素的右边乘积， arr[2] *= right 然后计算第1位右侧乘积 right *= nums[2]->right = 1 * 4
//第1个元素的右边乘积， arr[1] *= right 然后计算第0位右侧乘积 right *= nums[1]->right = 1 * 4 * 3
//第0个元素的右边乘积， arr[0] *= right 然后计算第 - 1位右侧乘积 - 1位已经不需要计算了
//循环完毕后，返回数组中的每个元素都是其他元素的乘积了 arr[2] *= 1； arr[1] *= 4; arr[0] *= 12
//方法 比特
int* productExceptSelf(int* nums, int numsSize, int* returnSize) 
{
	int* ret = (int*)malloc(numsSize * sizeof(int));
	*returnSize = numsSize;
	int left = 1, right = 1;
	//第一次循环，将当前位置左边的数字乘积填入返回数组中
	for (int i = 0; i < numsSize; i++) 
	{
		ret[i] = left;// 1 nums[0] nums[0]*nums[1] num[0]*nums[1]*nums[2] ....
		left *= nums[i];
	}
	//第二次循环，对于返回数组的元素从后往前进行，每次乘以右边元素的乘积
	for (int i = numsSize - 1; i >= 0; i--) 
	{
		ret[i] *= right; //最后一个成绩不需要乘以最后元素，乘以1就行
		right *= nums[i]; //right变化：1 nums[end] nums[end]*nums[end-1] .....
	}
	return ret;
}


//方法二
//int nums ={2, 3, 4};  前缀和思想
//先求出元素左边的乘积放到一个数组left[]中
//再求出元素右边的乘积放到一个数组right[]中
//最后再对应求乘积
int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int left[numsSize] = { 0 }; int right[numsSize] = { 0 };
    left[0] = 1;
    right[numsSize - 1] = 1;
    int i = 0;
    for (i = 1; i < numsSize; i++)
    {
        left[i] = left[i - 1] * nums[i - 1];
    }

    for (i = numsSize - 2; i >= 0; i--)
    {
        right[i] = right[i + 1] * nums[i + 1];
    }

    int* answer = (int*)calloc(numsSize, sizeof(int));
    *returnSize = numsSize;
    for (i = 0; i < *returnSize; i++)
    {
        answer[i] = left[i] * right[i];
    }
    return answer;
}